package com.ai.zuochengyun.phase01.class03;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化和反序列化树形结构
 */
public class Code12_SerializeAndDeserializeTree {

    /**
     * 先序 序列化
     *
     * @return
     */
    public static Queue<String> preSerialize(BinaryTreeNode head) {
        if (head == null) {
            return null;
        }
        Queue<String> ans = new LinkedList<>();
        preProcess(head, ans);
        return ans;
    }

    public static void preProcess(BinaryTreeNode head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(head.value + "");
            preProcess(head.left, ans);
            preProcess(head.right, ans);
        }
    }

    /**
     * 按前序方式 反序列化
     * @param queue
     * @return
     */
    public static BinaryTreeNode preDeserialize(Queue<String> queue) {
        if (queue == null || queue.isEmpty()) {
            return null;
        }
        return preRecover(queue);
    }

    public static BinaryTreeNode preRecover(Queue<String> queue) {
        String value = queue.poll();
        // 遇到null的叶子节点，就返回树的上一层
        if (value == null) {
            return null;
        }
        BinaryTreeNode head = new BinaryTreeNode(Integer.parseInt(value));
        head.left = preRecover(queue);
        head.right = preRecover(queue);
        return head;
    }

    /**
     * 按层方式序列化
     *
     * @param head
     * @return
     */
    public static Queue<String> levelSerialize(BinaryTreeNode head) {
        Queue<String> ans = new LinkedList<>();
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(head.value + "");

            // 总体和按层遍历节点类似，只是中间增加了保存value的逻辑
            Queue<BinaryTreeNode> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()) {
                BinaryTreeNode cur = queue.poll();
                // 没有左节点的时候，当前节点就不存放到queue队列中
                if (cur.left != null) {
                    queue.add(cur.left);
                    ans.add(cur.left.value + "");
                } else {
                    ans.add(null);
                }

                // 没有右节点的时候，当前节点就不存放到queue队列中
                if (cur.right != null) {
                    queue.add(cur.right);
                    ans.add(cur.right.value + "");
                } else {
                    ans.add(null);
                }
            }
        }
        return ans;
    }

    /**
     * 按层反序列化
     * @param nodeList
     * @return
     */
    public static BinaryTreeNode levelRecover(Queue<String> nodeList) {
        if (nodeList == null || nodeList.isEmpty()) {
            return null;
        }
        BinaryTreeNode head = generateNode(nodeList.poll());
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        if (head != null) {
            queue.add(head);
        }
        while (!queue.isEmpty()) {
            // queue里面永远保存的是非null的节点
            BinaryTreeNode cur = queue.poll();

            // 从nodeList头部的元素作为左节点
            cur.left = generateNode(nodeList.poll());
            // 从nodeList头部的元素作为右节点
            cur.right = generateNode(nodeList.poll());

            // 将非null的接口存入队列
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        return head;
    }

    private static BinaryTreeNode generateNode(String value) {
        if (value == null) {
           return null;
        }
        return new BinaryTreeNode(Integer.parseInt(value));
    }
}
